#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
int phi(int n)
{
	int ret = n;
	for (int i = 2; i <= n/ i; i++)
	{
		if (n % i == 0)
		{
			ret = ret / i * (i - 1);
			while (n % i == 0)
			{
				n /= i;
			}
		}
	}
	if (n > 1)
	{
		ret = ret / n * (n - 1);
	}
	return ret;
}